package LearnAlgorithm.h_标准数学公式;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/*
2 ~ n-1间是否有整数能整除n?
如果d是n的约数,那么n/d也是n的约数, 这是由n = d * (n / d)得到的；
d <= 根号n，这个等式在数学意义上已经有人证得，
所以检查		2 ~ 根号n		之间是否有整数能整除n就行了
 */
public class i判断素数 {
	public static void main(String[] args) {
		Map<Integer, Integer> primeFactor = primeFactor(100);
		printMap(primeFactor);
	}
	
	/**
	 * 最原始的判断素数
	 * @param num
	 * @return
	 */
	public static boolean isPrime(long num) {
		/*
		x <= y
		左右两边开方，不等式仍成立
		x * x <= y * y
		 */
		for (int i = 2; i * i <= num; i++) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 质因数分解
	 * @param num
	 * @return
	 */
	public static Map<Integer, Integer> primeFactor(int num) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 2; i * i <= num; i++) {
			while (num % i == 0) {
				Integer v = map.get(i);
				if (v == null) {
					map.put(i, 1);
				} else {
					map.put(i, v + 1);
				}
				num /= i;
			}
		}
		return map;
	}
	
	/**
	 * 人性化打印
	 * @param map
	 */
	public static void printMap(Map<Integer, Integer> map) {
		StringBuilder stringBuilder = new StringBuilder();
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			int k = entry.getKey();
			int v = entry.getValue();
			for (int i = 0; i < v; i++) {
				stringBuilder.append(" * " + k);
			}
		}
		System.out.println(stringBuilder.substring(3));
	}
}
